package cuppics;

import org.junit.Test;

public class Prj15 {

	/**
	 * Starting in the top left corner of a 2×2 grid, and only being able to
	 * move to the right and down, there are exactly 6 routes to the bottom
	 * right corner.
	 * 
	 * 
	 * How many such routes are there through a 20×20 grid?
	 */
	@Test
	public void test() {
		System.out.println(getNN(20));
	}

	/**
	 * ( 2n)!/ n!/n!
	 * @param n
	 * @return
	 */
	public long getN(int n) {

		long sum = 1;
		while (n > 1) {
			sum *= n--;
		}
		return sum;
	}

	/**
	 * // ( 2n ) * ( 2n - 1) /n / n 
	 * // 3 = 6, 4 = 8 
	 * // 6 * 5 * 4 = 20 
	 * // 3 * 2 * 1 
	 * // 8 * 7 * 6 * 5 = 70
	 * // 4 * 3 * 2 * 1
	 * 
	 * @param n
	 * @return
	 */
	public long getNN(int n) {

		if (n == 3)
			return 20;

		long sum = 20;
		for (int i = 4; i <= n; i++) {
			sum = sum * (2 * i) * (2 * i - 1) / i / i;
		}
		return sum;
	}

}
